/*************************************************************************
 * File Name:    Surrounded_Regions.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Wed 30 Oct 2013 11:41:48 PM CST
 * 
 * Description:  
 |-------------------------------------------------------------------------
 | Problem: Surrounded Regions
 |
 | Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
 |
 | A region is captured by flipping all 'O's into 'X's in that surrounded region .
 |
 | For example,
 | X X X X
 | X O O X
 | X X O X
 | X O X X
 | After running your function, the board should be:
 |
 | X X X X
 | X X X X
 | X X X X
 | X O X X
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
private:
    const int move[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public:
    void solve(vector<vector<char> > &board) {
        if (board.size() == 0) return;
        
        const int row = board.size();
        const int col = board[0].size();
        vector<vector<bool> > visited(row, vector<bool>(col, false));
        
        for (int i = 0; i < col; ++i) {
            if (!visited[0][i] && board[0][i] == 'O') dfs(0, i, board, visited);
            if (!visited[row - 1][i] && board[row - 1][i] == 'O') dfs(row - 1, i, board, visited);
        }
        for (int i = 0; i < row; ++i) {
            if (!visited[i][0] && board[i][0] == 'O') dfs(i, 0, board, visited);
            if (!visited[i][col - 1] && board[i][col - 1] == 'O') dfs(i, col - 1, board, visited);
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (!visited[i][j]) board[i][j] = 'X';
            }
        }
    }
    
    void dfs(int i, int j, vector<vector<char> > &board, vector<vector<bool> > &visited)
    {
        visited[i][j] = true;
        for (size_t k = 0; k < sizeof(move) / sizeof(move[0]); ++k) {
            int x = i + move[k][0];
            int y = j + move[k][1];
            
            if (x >= 0 && x < board.size() && y >= 0 && y < board[x].size() && board[x][y] == 'O' && !visited[x][y]) {
                dfs(x, y, board, visited);
            }
        }
    }
};

